HPAVC/HPAVC CD-ROM.iso/DN114_3D.ZIP/DN3D_1.DOC

Text File | 1996-02-03 | 25KB | 515 lines

=------------------------------[Intro to 3D Graphics Programming]--[Kiwidog]-=

 _____Greetings

 Hello everyone,

 As my first code article since joining the Hornet crew, I've decided to
 write an introduction into 3D graphics coding.  Trixter informed me that
 DemoNews has never had a 3D article, so it seemed like a good idea. :-)

 This will not be just one article - far from it.  In fact, it will take
 quite a few articles to cover all the information I want to cover (after
 finding out about space limitations on article size I'm allowed to write,
 I've had to chop up the series into smaller pieces).  But expect a minimum
 ten or so articles coming your way...

 This is the full version of the DemoNews 114 article, which means you've
 got the supplement file (that's good, because it has example source, too :)
 The source included is the same example, but in three different files,
 depending on what language and compiler you use.
    WC_EX1.C - Watcom C version (32-bit DOS extended)
    BC_EX1.C - Borland C version
    TP_EX1.PAS - Turbo Pascal version

 This series will assume you've never done 3D graphics (or "Vectors" as
 the scene likes to call it) before.  I'm going to try this on a very basic
 level, and if you're already familiar with the essentials, you might want
 to hit PgDn a few times.  Eventually, I'll write about more complicated 3D
 issues in later articles.  But let's take it one step at a time...

 _____What You Need To Know First

 I'm assuming you have a knowledge of basic algebra, i.e. early high school
 level math.  If you've had some Trigonometry already, that will help out,
 but I'll try to cover the basics of what you need from that as well.  But,
 more important than any one particular requirement, you have to like math,
 or at least a willingness to like it.

         MATH IS ONLY BORING IF YOU DON'T HAVE A USE FOR IT.

 Basically, 3D coding is not really about programming... it's almost entirely
 about math.  The amount of time you spend thinking about what you're doing
 is generally a lot longer than the time you actually spend pounding the keys
 writing the code.

 If you don't think you like math, and you're a coder, chances are you
 probably _DO_ like math and just don't know it. :-)  I'm serious... a lot
 of times when you hate a subject in school, you don't really hate it, you
 just think you hate it because you hate the way it's taught.  Once you get
 down to finding a purpose for all that "useless" knowledge.... it becomes
 a heck of a lot of fun.  So if you like math, and you like coding graphics,
 you've come to the right place.  If you like coding graphics but don't like
 math... give it a chance; you may find out something new about yourself. :-)

 _____What You Don't Need to Know First

 Okay, generally speaking, the chain of math courses taught in high school
 and college (or their European equivalents, which I can't really speak for
 but I can take a guess) goes something like this:

 1. Algebra   2. Geometry   3. Analytical Algebra  4. Trigonometry
 5. Pre-Calculus   6. Calculus   7. Linear Algebra   8. Vector Geometry
 9. Multivariable Calculus   10. Differential Equations   11. Even more
 complicated issues that I haven't gotten to yet...

 You need to know up to #3 to make use of any of this.  #4 would be helpful,
 although I'll cover a few things here in the beginning to get you going,
 if you've never taken Trig before.

 Pre-Calc and Calc aren't directly needed for this series, although you'll
 find it useful later on in life when you want to make really cool movements
 for your vectors.  And if you know through #7, life is a breeze; you can
 forget most of this beginning crap. :) Anything after that I'm not going to
 cover by itself, but you'll find it helpful if you know it, as you try more
 innovative ideas with your vector code.  But still, it's not necessary at
 all for the little I'm going to be able to teach you. :)

 _____What Will Be Covered In This Series

 Whew, it's a whopper.  Here's the series layout as I'm planning it so far.
 As you can tell, the first couple articles are for the _very_ beginners,
 like the kind who know how to code, but have never even touched anything
 with 3D before.  After the first few, it'll get more interesting though,
 so bear with me (if you have some 3D experience already, you can forget
 reading the first few articles; they won't do you any good).

 1. Basic Trig functions, 3D Coordinate to 2D Screen Projection.
 2. 2D and 3D Rotations & Other Transformations.
 3. Dot and Cross Products, Backface Removal and Lightsourcing.
 4. Polygon Fills - Flat and Lambert
 5. Polygon Fills - Gouraud and Phong
 6. Polygon Fills - Affine Texture Mapping
 7. Polygon Fills - Perspective Texture Mapping, Perspective Correction
 8. Spherical and Cylindrical Coordinates
 9. Polygon Fills - Bump Mapping
 10. BSP Trees and Spacial Partitioning
 11. Polygon Fills - Reflection Mapping
 12. Alternative Camera Positioning and Motion
 13. Path Management, Linear and Bezier Curve Movement
 14. Basic Inverse Kinematics
 15. (Unknown - I'm not sure how much further I can take it without risking
      losing the few tricks I have up my sleeve for my future :)

 It's quite likely that the later articles will be split into separate
 articles as well (I doubt I can fit both Gouraud and Phong, for example,
 into one article).  So the numbers are probably going to get higher and
 higher.  It will probably be around the time of NAID or afterward that
 the series ends.

 Get ready for a crash course in 3D... :-)


 _____Section One - Basic Trigonometric Functions


 Okay, If you've taken Trig before, skip this section.  If you haven't,
 you're probably thinking that this long title doesn't sound too friendly.
 Don't worry, it sounds a whole lot worse than it is.

 The main principles of Trigonometry come from the first part of the name,
 "Trigon", which pretty much means a triangle.  Everything in Trig is based
 on a few functions which deal with triangles.  There are six of these
 functions...

 Sine, Cosine, Tangent, Secant, Cosecant, and Cotangent
 Abbreviated:  Sin, Cos, Tan, Sec, Csc, and Cot.

 ... but in fact, they all boil down to the first two, Sine and Cosine.

 Now I assume you're all familiar with functions, like [f(x) = 2x] and so
 forth (BTW I'll enclose functions in [] on occasion throughout this doc).
 Well the Trig functions are all functions using angles, for example
 [f(x) = sin(x)]  or even  [f(x) = 2 sin(x) - 5 cos(x)], and so on.
 In these cases, x is an angle, either in degrees or radians.  I'm going
 to stick with degrees for this explanation, since radians are too complex
 for me to discuss right now.

 Okay, so now you're thinking, "Great... Sine and Cosine are functions using
 angles.  But what do they _DO_?"  Well, here's the rundown.

 Get out a piece of paper.  Go ahead, I'll wait.  Now on that piece of paper,
 draw yourself a pair of X and Y coordinate axes, like you normally would for
 a graph.  Make it big, so you give yourself lots of room.

 Now draw a circle around the origin.  Make it as good a circle as you can
 sketch.  Now whatever size you drew your circle, assume that's a radius
 of 1.  So where the circle hits your X and Y axes, label those points as
 X=1 on the right, Y=1 on the top, X=-1 on the left, and Y=-1 on the bottom.

 Okay, with this circle, we need some angles.  Using your good ol' 360-degree
 system, label those four points with their angles, where 0 degrees is facing
 the right and they go counterclockwise.  So 0 is at the right, 90 is up,
 180 is left, and 270 is down.

 Now knowing that's how the angles go, draw a line from the origin out to the
 circle at about, oh, 60 degrees (up and to the right, more tall than wide).
 At that point on the circle, draw a line STRAIGHT DOWN to the X axis.  What
 you should have now is a triangle inside the circle, with one side on the
 X axis, one going straight up, and one at a 60 degree angle.

 Okay, it's time for a little guessing game.  Assuming that the circle has
 a radius of 1 like you drew it, how tall is that vertical side of the
 triangle?  It's almost as tall as the circle, but not quite... more than
 half the height of the circle, maybe around 3/4 the height, something like
 that.

 What was your guess?  Probably somewhere between 0.7 and 0.9, I would think.
 It should look about that tall.  Whatever your guess is, write it down, and
 keep it handy... it's going to be very important.

 Now do the same thing for the bottom horizontal side of the triangle, the
 one along the X axis.  How long is that from the looks of it?  It appears
 around half the width of the circle, so you'd probably guess around 0.5 or
 so.  Anyway, write that one down too.

 Okay, So you've got this triangle inside this circle, with the longest side
 at an angle of 60 degrees and a length of 1 (the radius of the circle),
 and two sides going straight vertical and horizontal, with lengths somewhere
 near the numbers you guessed.

 I'm gonna pull out my calculator, which supports Trig functions.  Lemme
 punch up the numbers....

    Sin(60) = 0.8660254
    Cos(60) = 0.5000000

 Notice any correlation?  You should... they're the lengths of the sides you
 were guessing! :-)  That, quite simply, is what the Sin and Cos functions
 are... if you have a circle with radius 1, and a line at any angle from
 the origin to the circle, then the Sine of that angle is the Y-component
 (height) of that line, and the Cosine of the angle is the X-component
 (width) of the line.

 Other examples?  Well now that you know what the Sin and Cos functions mean,
 what are the Sin and Cos of 90 degrees?  Well let's see... that's the line
 going straight up from the origin, along the Y axis.  The height is
 the height of circle, exactly.  And the width... well, there is no width,
 since it's not going left or right whatsoever.

 Sure enough,

    Sin(90) = 1.0000000
    Cos(90) = 0.0000000

 Likewise, the trend continues.....

          Angle        Sine    Cosine
          0        0    1
          90        1    0
          180             0    -1
        270        -1    0

 Which demonstrates a very important point about these functions

    Fact: The Sine and Cosine functions will never go less than -1,
          and never greater than 1.

 ... and that makes sense, considering the circle has a radius of 1.
 (Terminology: The circle you drew is often called the "unit circle" by
  math books and teacher-type people).

 Now by looking at the circle, you can see how the height changes less and
 less as you approach Sin=1 or Sin=-1, and likewise the width changes less
 and less as you approach Cos=1 or Cos=-1.  It turns out that the Sin and
 Cos functions are not linear whatsoever... and because of that, calculating
 them for any given angle is a real pain in the rear.  Sure, you have the
 occasional angles like 90 and 180 which have 1s and 0s, or 30 and 60 which
 have one of the components exactly 0.5, but most of the time you have values
 that are not the nicest of numbers.

 For this reason, you often hear 3D coders referring to "Sine Tables", which
 are precalculated tables holding the Sin and Cos values for every angle in
 their system (in this example, a 360 degree system.  It turns out in coding
 that a 256 degree system is much more convenient, for reasons you can
 probably guess).  These do-it-once tables turn an otherwise painful
 calculation into a simple memory look-up. :-)

 (BTW - earlier I mentioned in addition to Sin and Cos the Tan, Sec, Csc
 and Cot functions... these can all be created from Sin and Cos by the
 following:    Tan(x) = Sin(x)/Cos(x)
        Sec(x) = 1/Cos(x)
        Csc(x) = 1/Sin(x)
        Cot(x) = Cos(x)/Sin(x) = 1/Tan(x)
 Most of those aren't very useful in vector coding, with the exception of
 Tangent... it will come in handy at times.  Everything else isn't too
 important for now, but keep it on the back burner for future reference).

 Okay, so now you've learned what you need to know from Trig... that the
 Sin and Cos functions can be used to find the X and Y parts of a line at
 any given angle.  You just take the length of the line, multiply the Sin
 or Cos (whichever you're looking for, Y or X respectively) by the line's
 length, and wham you've got your result.  This will be used EXTENSIVELY
 in the rest of the doc and in 3D in general, as almost everything depends
 on these components.

 There is certainly a lot more to trigonometry, and entire books have been
 dedicated to the subject.  My highly over-simplified version here should
 hopefully be enough to get your foot in the door.  If you want more
 complex and detailed info, I'd highly suggest a good math textbook covering
 the subject (Trig is often grouped in with pre-calculus texts, incase you
 have a difficult time finding a separate book).  But this should be good
 enough for the time being. :)

 All set?  Then let's get out of this plane of thought (sorry, very bad pun)
 and get into some three-space nitty gritty, starting with...


 _____Section Two - The 3D Cartesian Coordinate System


 Okay, you're undoubtedly already used to doing graphics in 2D using the X
 and Y axes; it's what you've been doing in algebra all along.  Well using
 X and Y is the 2D standard of the Cartesian coordinate system, and likewise,
 we need to add another axis of depth for 3D - The Z axis.  But where does
 this Z axis go?

 Well X and Y are perpendicular to each other in the 2D plane.  It's the same
 as the plane of your screen, for example.  Well in 3D, we can get depth by
 putting the Z axis perpendicular to that entire plane altogether, going
 either into or out of your screen.

 A common term for a line or plane perpendicular to another plane is
 "orthogonal".  That is, we want a Z axis that's orthogonal to the XY screen
 plane.

 But in which direction?  It can either go into or out of the plane, so which
 one is right?  Well this is really entirely by convention... the standard
 way is to use a "right handed" orientation.  What's a right handed
 orientation?  Okay, hold up your right hand in front of your face.  Point
 your thumb toward your nose.  Now look at your fingers... they curl
 counterclockwise.  This is the basis behind a right-handed system.  When you
 have the XY plane, the two axes for X and Y are to the right and going up,
 respectively.  So if you start your hand at the first axis, X, and curl your
 right hand's fingers in the direction of the second axis, Y, your thumb
 will point out toward your nose.

 So the Z axis goes out of the screen, toward you, by a right-handed system
 (for the same reason, if you used the YX plane instead of the XY plane,
 the curl would be in the opposite direction and Z would go into the screen
 instead).

 Cheesy ASCII graph....

        Y
        |
        |
        | Screen Plane
        |
        |
            -------X
           /
          /
         /
        Z


 The graph above is the way we're going to do it in this doc.  All 3D
 Cartesian really is, is just the same coordinate system you're used to, but
 with the added dimension so you can locate a point anywhere in space and
 not just on a plane.  End of story (You might find later that other
 coordinate systems, like spherical and cylindrical, can help out with some
 routines... but I'll go over those in time).

 Short section, eh?  There's more, but not much. :-) Well, now with the 3D
 system in your grasp, it's time to put it to use, and get some 3D points to
 show up on-screen.


 _____Section Three - Perspective Projection


 Now we've got this nice XYZ spacial coordinate system... but how do we take
 advantage of it and get some stuff on-screen from it?  In 2D, it was easy...
 you just used the same X axis as in your coordinates, and the Y axis was the
 same only flipped upside down (since as you know, in coding it's easier if
 the Y axis goes down, for calculation reasons).  But how are we going to
 take this Z thing into account and make things look right?

 The way we do it is by "Perspective Projection".  Perspective is a pretty
 basic idea which you see continuously in your life.... Things further away
 from you look smaller than things closer up.  Pretty obvious fact that you've
 lived with throughout your existence. :)

 Well all we have to do is turn that simple principle into math...

 English way:    "Things further away from you look smaller than things
        closer up."

 Math way:    "The projected size of any object in the eye is inversely
        proportional to its distance from the eye".

 It's more "math-like", but still makes sense, right?  They both mean the
 same thing more or less, but the second phrase is more easily turned into
 equation form... the kind we can put into our code.

 Okay, by our ASCII graph of the coordinate system, your eye lies right along
 our Z axis, staring down in the negative direction (the Z axis goes out of
 your screen, and you're looking in).  So an object's, or point's, distance
 from the eye is going to have a lot to do with the Z coordinate of that
 point.

 So the first thing we need to settle is, if our eye (or in our case, the
 video screen) is sitting somewhere along the Z axis.... where along the Z
 axis is it?  In truth, this is entirely up to you... the screen is just
 a "camera", and we're trying to find a convenient place for it to sit.
 All we know is that it goes along the positive Z axis.

 It turns out for calculation reasons that a very effective place to put the
 camera is at Z=256.  You'll see why in a minute... (and no, none of this
 is carved in stone.  Cameras can go anywhere and view in any direction,
 it's just that the math gets more complicated).

 Okay, now we've got the camera at (0,0,256) and pointing in the negative
 direction.  That means that our Cartesian origin is exactly 256 units away
 from us, right along our line of sight.  The next thing we need to make up
 is a frame of reference for X and Y.... How big, visually, is a unit along
 X or Y?  Well we can use any set of values we see fit, but just to make it
 easier on the brain, we want to use something we're already used to...
 something intuitive...

 How about 1 pixel?  It's easy to compute, since it's the same as your
 screen plane.  Okay, so we know _somewhere_ viewable along this axis, X and
 Y are going to mean 1 pixel units.

 But where along the Z axis?  If things get larger as they get closer and
 smaller as they get further away, where's a good distance to say where the
 unit/pixel plane sits?

 Heck, why not just use the Z=0 plane?  After all, we know the origin is
 perfectly visible (256 units down the -Z axis) so the origin is easily in
 reach, and probably will make it easy to calculate our perspective viewing.

 Okay, we've got all we need to set up some perspective equations.  Now let's
 do some simple examples in our heads so we can find out where these
 equations are coming from...

 In 320x200 resolution (you can use any resolution you want, really, but this
 is just for demonstration), the center point of your screen is at (160,100).
 Makes sense, and you're probably very used to this by now.  Well, we're
 viewing along the -Z axis, so that's where our axis is going down.  Right
 along the line of that pixel.  No up, no down, no left, no right.  That's it.

 Now we know that at Z=0, Every X and Y unit mean one pixel.  So where would
 (5,5,0) be positioned?  Well, it's the same as our screen plane, so there's
 no distance adjustments to do.  It's 5 to the right of the origin, so
 ScrX=160+5 = 165.  And it's 5 above the origin, which is in the opposite
 direction of our "screen plane" Y, so that's ScrY=100-5 = 95.  You've got
 your projected point.

 So what to do with points not on Z=0?  Howsabout (5,5,128)?  Well if we
 think about it, Z=0 is 256 units distance from the screen.  Well Z=128 is
 256-128 = 128 units distance from the screen.  Exactly half of the distance.

 Half the distance?  That makes it twice the size! :-)  So instead of adding
 5 to X and subtracting 5 from Y, you'd use 10 instead for each axis.  That
 would give us screen coords (170,90) for this point.  Same 3D X and Y as in
 the first example, but the fact that it's so much closer makes it look
 further from the center of the screen... the essence of perspective. :)

 Now in general, our equations go something like this

    ScrX = ( Lens*X / Distance ) + CenterX
    ScrY = CenterY - ( Lens*Y / Distance )

 I'll explain each piece.  First, ScrY _would_ be the same basic equation
 as ScrX, except that we have to do the subtraction instead because Y goes
 down onscreen, not up.  Anyway, we have a few variables here...

 ScrX and ScrY are the screen point of the 3D point we're trying to project.
 I figure you guessed that one already. :-)

 Distance is the distance of the point from the eye.  As we discussed before,
 this has a _direct_ correlation to the Z coordinate of our 3D point.  Now
 since we're on the positive Z axis but viewing in the negative direction,
 and we know that at Z=0 the distance is 256, then any point where Z > 0
 will have a distance < 256.  Likewise, if Z < 0, the point will be further
 away than the origin, and distance > 256.  This makes distance a very
 simple value:

    Distance = (256-Z)

 Pretty easy, eh? :-)  Now, Lens is a multiplier used to give your projection
 the right "field of view" that you want.  You can manipulate Lens to give
 the projection a very narrow range of vision, or to give it the classic
 "wall-eye" view as well.  But in general, a really messed-up field of view
 will make people want to vomit.  It's not natural.

 So we want to set it to something that will "feel" natural.  Well, from our
 calculations and the fact that we want a unit/pixel relationship at Z=0,
 we can get our Lens factor immediately... 256.  It's also a nice multiplier,
 as you can use bit-shifts to get it, instead of a costly MUL instruction.

 And finally, CenterX and CenterY are positive integers that match to the
 center X and Y point onscreen; 160 and 100 in this case (the Center value
 for any resolution is just the resolution/2, which makes sense).

 So, from there, our equations boil down to

    ScrX = ( 256*X / (256-Z) ) + 160
    ScrY = 100 - ( 256*Y / (256-Z )

 The first thing you should recognize is that we don't need to calculate
 (256-Z) twice.  Also, if you use fixed point, you can calculate the divide
 only once as well, but that's for a later article (I'm not focusing on
 optimizations in this one).  Anyway, let's work out one of our previous
 examples using these equations and see if we get the same result.  How about
 the (5,5,128) one...  let's see...

    Distance = 256-Z = 256-128 = 128

    ScrX = ( 256*X / 128 ) + 160
         = ( 256*5 / 128 ) + 160
         = 10 + 160
         = 170

    ScrY = 100 - ( 256*Y / 128 )
         = 100 - ( 256*5 / 128 )
         = 100 - 10
         = 90

 Yup, same answer!  And these equations go quite easily into code. :-)

 Now you'll find that using straight integer math with these equations will
 work well at first, but there are added advantages to using fixed point
 math as well.  If you're familiar with fixed point, you should have few
 problems trying to adapt this to it, speeding things up in the process.
 If you're not familiar with it, don't sweat it; I'll cover it in an
 upcoming article.

 Well, looks like that's the end of this article... make sure to check out
 the sample source in Pascal and C within this supplement, and try a few
 experiments out on your own!  You'll want to get very familiar with
 projection as we get into more advanced stuff later on... and since it's
 at least a week until the next DemoNews, you've got the time, so take
 advantage of it. :-)

 Next issue, it'll be time to start on our path to not just getting these
 points up there, but getting them to move.  Straight movement left, right,
 up, down, in and out is easy... you just add or subtract from X, Y, or Z.
 But rotation, that's another story.

 Until next time,


 Chris Hargrove
 a.k.a. Kiwidog, of Terraformer & Hornet
 Coding & Organization
 email: <[e-mail]>